package com.heima.leetcode.practice;

/**
 * leetcode 28 找出字符串中第一个匹配项的下标
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/10 20:32
 */
public class E28 {

    /**
     * <h3>方法一：遍历每种可能 0ms</h3>
     * 缺点就是会进行很多不必要的匹配
     * @param haystack 目标字符串
     * @param needle 待匹配字符串
     * @return 匹配到的下标，未匹配到返回-1
     */
    public int strStr1(String haystack, String needle) {
        char[] origin = haystack.toCharArray(); // 原始字符串
        char[] pattern = needle.toCharArray(); // 模式字符串
        for (int i = 0; i < origin.length - pattern.length + 1; i++) {
            if (origin[i] == pattern[0]){
                boolean find = true; // 标记是否找到匹配项
                for (int j = 1; j < pattern.length; j++) { // 匹配后面的项
                    if (origin[i + j] != pattern[j]){
                        find = false;
                        break;
                    }
                }
                if (find){
                    return i;
                }
            }
        }
        return -1;
    }

    /**
     * <h3>方法二：KMP算法，跳过一些不必要的比较 0ms</h3>
     * 这个算法的核心是最长相同前后缀长度，i用来表示原始字符串的索引，初始值是0
     * j用来记录模式字符串的索引，初始值是0，如果i和j当前匹配到的字符相等
     * 则i++，j++，如果但前匹配到的字符不相等，让j回退到合适的位置，避免重复比较
     * 回退的规则就是模式字符串前j个元素的前缀和后缀相等的最大长度（索引从0计数）
     * 继续比较当前i和退回后的j，如果相等，继续匹配，否则，继续让j回退，直到j=0，
     * 相等还是加1，不相等则i和j都加一。最终i要小于原始字符串的长度，否则返回-1
     * 如果找到j=模式字符串的长度说明找到解了，返回i - j，此时i和j处于字串
     * 在原始串中的位置的最后一个字符的后一个
     * @param haystack 目标字符串
     * @param needle 待匹配字符串
     * @return 匹配到的下标，未匹配到返回-1
     */
    public int strStr2(String haystack, String needle) {
        char[] origin = haystack.toCharArray(); // 原始字符串
        char[] pattern = needle.toCharArray(); // 模式字符串
        // 指定范围内最长相同前后缀长度
        // 例如         字符串： a   b   c   a   b   c   d
        // 最长相同前缀后缀长度： 0   0   0   1   2   3   0
        //                索引： 0   1   2   3   4   5   6
        int[] longestCommonPrefixSuffix = longestCommonPrefixSuffix(pattern);
        int i = 0; // 原始字符串的索引
        int j = 0; // 模式字符串的索引
        while (pattern.length - j <= origin.length - i){ // 待匹配的模式串长度要小于等于剩下的原始字符串的长度，再进行匹配
            if (origin[i] == pattern[j]){ // 匹配成功，都自增1
                i++;
                j++;
            } else if (j > 0) { // 匹配失败，并且有可能回退j，从而跳过一些元素
                j = longestCommonPrefixSuffix[j - 1]; // j跳转到的位置应当是相同前缀部分后一个位置
            } else { // 匹配失败，并且j=0，说明当前字符和模式串的第一个字符不相等，则i自增1，继续匹配，j不自增，下次还要和j=0相比
                i++;
            }
            if (j == pattern.length){ // 不能写在循环外，当最后一段匹配成功时，i=origin.length+1，j=pattern.length+1，while判断的时候会成立，从而进入循环
                return i - j; // 匹配成功，返回i-j，此时i和j处于字串在原始串中的位置的最后一个字符的后一个
            }
        }
        return -1; // 匹配失败，返回-1
    }

    /**
     * <h3>方法三：KMP算法，跳过一些不必要的比较 比较与第二种，while循环条件有所不同 0ms</h3>
     * 这个算法的核心是最长相同前后缀长度，i用来表示原始字符串的索引，初始值是0
     * j用来记录模式字符串的索引，初始值是0，如果i和j当前匹配到的字符相等
     * 则i++，j++，如果但前匹配到的字符不相等，让j回退到合适的位置，避免重复比较
     * 回退的规则就是模式字符串前j个元素的前缀和后缀相等的最大长度（索引从0计数）
     * 继续比较当前i和退回后的j，如果相等，继续匹配，否则，继续让j回退，直到j=0，
     * 相等还是加1，不相等则i和j都加一。最终i要小于原始字符串的长度，否则返回-1
     * 如果找到j=模式字符串的长度说明找到解了，返回i - j，此时i和j处于字串
     * 在原始串中的位置的最后一个字符的后一个
     * @param haystack 目标字符串
     * @param needle 待匹配字符串
     * @return 匹配到的下标，未匹配到返回-1
     */
    public int strStr3(String haystack, String needle) {
        char[] origin = haystack.toCharArray(); // 原始字符串
        char[] pattern = needle.toCharArray(); // 模式字符串
        // 指定范围内最长相同前后缀长度
        // 例如         字符串： a   b   c   a   b   c   d
        // 最长相同前缀后缀长度： 0   0   0   1   2   3   0
        //                索引： 0   1   2   3   4   5   6
        int[] longestCommonPrefixSuffix = longestCommonPrefixSuffix(pattern);
        int i = 0; // 原始字符串的索引
        int j = 0; // 模式字符串的索引
        while (pattern.length - j <= origin.length - i
                && i < origin.length
                && j < pattern.length){ // 待匹配的模式串长度要小于剩下的原始字符串的长度并且i和j小于原始和模式字符串的长度，再进行匹配
            if (origin[i] == pattern[j]){ // 匹配成功，都自增1
                i++;
                j++;
            } else if (j > 0) { // 匹配失败，并且有可能回退j，从而跳过一些元素
                j = longestCommonPrefixSuffix[j - 1]; // j跳转到的位置应当是相同前缀部分后一个位置
            } else { // 匹配失败，并且j=0，说明当前字符和模式串的第一个字符不相等，则i自增1，继续匹配，j不自增，下次还要和j=0相比
                i++;
            }
        }
        return j == pattern.length ? i - j : -1; // 匹配成功，返回i-j，此时i和j处于字串在原始串中的位置的最后一个字符的后一个
    }

    /**
     * 构建最长相同前后缀长度数组
     * @param pattern 模式串
     * @return 最长相同前后缀长度数组
     */
    private int[] longestCommonPrefixSuffix(char[] pattern) {
        int[] result = new int[pattern.length]; // 记录索引0-i范围最长相同前后缀长度
        int i = 1; // result的索引，从1开始，因为0索引处值肯定是0
        int j = 0; // 模式串的索引
        while (i < pattern.length){
            if (pattern[i] == pattern[j]){ // 匹配成功，记录长度，i自增1，j自增1
                result[i++] = ++j;
            } else if (j > 0) {
                j = result[j - 1]; // 匹配失败，并且j不等于0，回退j，因为j前面的是已经处理好了的
            } else {
                i++; // 匹配失败，并且j=0，说明当前字符和模式串的第一个字符不相等，则i自增1，继续匹配，j不自增，下次还要和j=0相比
            }
        }
        return result;
    }
}
